
/*
 * Question: Try to propose an non-recursive algorithm that traverse a
 * binary tree in preorder or inorder.
 */

#include <iostream>
#include <stack>
using namespace std;

#include "bitree.h"

class bitree : public _bitree<bitree, char> 
{
};

void visit(bitree *rt)
{
    cout << rt->key << " ";
}

void preorder(bitree *rt)
{
    stack<bitree *> s;
    bitree *p;

    p = rt;
    while (p || !s.empty()) {
        if (p) {
            visit(p);
            s.push(p);
            p = p->lchild;
        } else {
            p = s.top(); s.pop();
            p = p->rchild;
        }
    }
}

void inorder(bitree *rt)
{
    stack<bitree *> s;
    bitree *p;

    p = rt;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            p = p->lchild;
        } else {
            p = s.top(); s.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

int main()
{
    bitree *rt;

    bitree_create<bitree,char>(rt, "ex37.txt");
    preorder(rt);
    cout << endl;
    inorder(rt);
    cout << endl;
    bitree_destory(rt);
    return 0;
}
